Web log de Serge Boisse
On line depuis 1992 !
Auteur : Serge Boisse
Etant donné une séquence ou un flux de symboles (incoming stream),
On s'intéresse ici uniquement aux compressions par détection de répétitions.
Essayons de voir ce qui se passe quand on rajoute un symbole
On utilisera ici la syntaxe "latex", pour les répétitions, c'est à dire que par exemple la séquence 101011101011 sera compressée par ((10)^{2}1^{2})^{2}, soit en latex
Les '()' peuvent être omises s'il s'agit de la répétition d'un symbole unique : 1^2 ou (1)^2. De même
Soit
Soit (ab^{n})^{m}, et
Dans ce document, nous nous aurons besoin d'une syntaxe pour comprendre cet algorithme :
On utilisera des règles de réécriture de la forme
Un filtre
Par exemple le filtre
Une règle aura la forme
autrement dit pour toute règle de la liste ci-dessous, qui sont de la forme
exception : La règle "par défaut"
Pour appliquer une règle à
Par exemple pour appliquer la règle
Dans certains cas, plusieurs règles seront applicables.
On retiendra celle ou celles qui matchent la sous-chaine finale
Ensuite, parmi leurs résultats, on retiendra celui qui donne la chaine de plus faible complexité (s'il y en a plusieurs, on choisit au hasard ou la première).
En effet une mème séquence
Mais
est meilleure parce qu'elle compresse une partie de plus proche de l'origine.
Existe-t-il une liste finie de règles permettant de traiter tous les cas ?
Je pense que oui parce que au fur et a mesure qu'on ajoute des règles, il devient de plus en plus difficile d'en trouver une qui ne soit pas un sous-cas d'une autre.
Par exemple je voulais ajouter
En fait, on n'a jamais besoin des suites de symboles
Essayons de bâtir cette liste :
Si la chaîne
11.
12.
13.
14.
15.
16.
17.
cas particulier,
est-il mieux que ? Non.
Sinon si
Sinon si S se termine par une chaîne dont le dernier symbole après expansion est
en fait il n'y a pas de règles "intéressante" dans ce cas. En effet,
se termine forcément par ou ou
Mais
ne simplifie rien et idem, idem
Sinon le dernier symbole de
donc
se finit par ou ou
Le programme : cf. ci-dessous algorithme incrémental
Exemple : #TBC
11101101110110110110
1+1 -> 1^{2} (11)
1^{2} => 1^{3} (21)
1^3+0 =>1^{3}0 (11)
1^{3}0+1 =>1^{3}01 (11)
1^{3}01+1 => 1^{3}01^{2} (12)
1^{3}01^{2}+0 => 1(1^{2}0)^2 (42)
1(1^{2}0)^{2}+1 => 1(1^{2}0)^{2}1 (11)
Il s'agit, à partir d'une séquence déjà compressée à laquelle on ajouterait un nouveau symbole, de calculer la nouvelle séquence compressée.
Pour simplifier le programme on imposera que s^{n} et si X a plus d'un symbole, (X)^{n}
Entrer une séquence initiale déjà compressée (comme 1^{2}), et un nouveau symbole (comme 1) . Le programme essaye de compresser la nouvelle chaine obtenue
page créée le 18/03/2025 à 15:09modifiée le 17/03/2025 à 11:32
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.